import sys
import Image
import ImageDraw

class Vector:
	"""Simple Vector class with cross-product functionality

	"""
	px = 0.0
	py = 0.0

	def __init__(self, px, py):
		self.px = px
		self.py = py	

	def cross(self, v2):
		return (self.px * v2.py) - (self.py * v2.px)
	

class Point:
	"""Simple Point class with an equals method and a minus method that
	returns a vector.

	"""

	x = 0.0
	y = 0.0
	def __init__(self, x, y):
		self.x = x
		self.y = y

	def equals(self, other_point):
		return (self.x == other_point.x and self.y == other_point.y)

	def minus(self, p2):
		return Vector(self.x - p2.x, self.y - p2.y)


def bottom_most(S):
	"""Finds the bottom-most point in a set of Points, S
	"""
	index = 0;
	for i in range(len(S)):
		point = S[i]
		if point.y < S[index].y:
			index = i
		
	return S[index]


def jarvis(S):
	"""Function returns the points that make up the convex hull of the
	list of points passed into the function.

	"""

	if len(S) <= 3:
		return S

	P = [bottom_most(S)]
	endpoint = S[0]
	if P[0].equals(endpoint):
		endpoint = S[1]	
	i = 0
	while not endpoint.equals(P[0]):
		endpoint = S[0]
		if P[i].equals(endpoint):
			endpoint = S[1]	
		AB = endpoint.minus(P[i])

		# Finds the line segment AB such that all the points
		# are to the left of that segment
		for j in range(len(S)):
			AC = S[j].minus(P[i])
			# If the cross product is negative, then the new point
			# is more towards the outside of the hull than the last
			if AB.cross(AC) < 0.0:
				endpoint = S[j]
				AB = endpoint.minus(P[i])

		P.append(endpoint)
		i += 1
				
	# Returns all but the last point, because Python doesn't have
	# a do-while loop, and I'm lazy
	return P[0:len(P)-1]


if __name__ == '__main__':
	f = open(sys.argv[1], 'r')
	f_str = f.read();
	f.close()
	S = []
	for line in f_str.split("\n"):
		line = line.strip('\n')
		vals = line.split("\t")
		if len(vals) == 2:
			S.append(Point(float(vals[0]), float(vals[1])))

	# Get the convex hull
	P = jarvis(S)

	im = Image.new("RGB", (500, 500))
	draw = ImageDraw.Draw(im) 

	# draw the concave hull in red
	for (p1,p2) in zip(P[0:], P[1:]):
		p1x = (p1.x + 250)
		p1y = (p1.y + 250)
		p2x = (p2.x + 250)
		p2y = (p2.y + 250)
		draw.line((p1x, p1y, p2x, p2y),(255,0,0))
	
	# draw the last line	
	p1x = P[-1].x + 250
	p1y = P[-1].y + 250
	p2x = P[0].x + 250
	p2y = P[0].y + 250
	draw.line((p1x, p1y, p2x, p2y),(255,0,0))

	# draw points in white	
	for point in S:
		px = (point.x + 250)
		py = point.y + 250
		draw.point((px,py),(255,255,255))

	im.show()

	

	# Just printing the points in the convex hull for now.
	for point in P:
		print '(%.5f %.5f)' % (point.x, point.y)

	print "Invalid File Name"

